package leetcode_ago.top_k;
/**
 * 前k个高频单词
 * 给定一个单词列表words和一个整数k，返回前k个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序。
 */
import java.util.*;

/**
 * 分析：1.前k个出现次数多的单词，topK,用最小堆
 * 2.比较的是次数，用到Map集合【注意次数相等情况，此时比较的是单词典序，要让典序小的单词留下，大的出队。
 * 但是比较次数时的小堆判断时，是小的不入队大的入队，所以要o2.compareTo(o1)让认为小的其实是大的（即让默认的升序字典序变为降序了）】
 */
public class Num692_TopKFrequentWord1 {
    private class Freq{
        String word;
        int times;
        public Freq(String word, int times) {
            this.word = word;
            this.times = times;
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        //1.单词存储到Map集合
        Map<String,Integer> map=new HashMap<>();
        for(String i:words){
//            map.put(i,map.getOrDefault(i,0)+1);
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else{
                map.put(i,1);
            }
        }
        //2.遍历Map集合，前k个高频单词放入堆中
        Queue<Freq> queue=new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                if(o1.times==o2.times){
                    return o2.word.compareTo(o1.word);
                }else{
                    return o1.times-o2.times;
                }
            }
        });
        for(Map.Entry<String,Integer> entry: map.entrySet()){
            if(queue.size()<k){
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else{
                Freq freq= queue.peek();
                if(entry.getValue()<freq.times){
                    continue;
                }else if(entry.getValue()== freq.times){
                    //频次相等，要比较单词，小的元素入队
                    if(entry.getKey().compareTo(freq.word)<0){
                        queue.poll();
                        queue.offer(new Freq(entry.getKey(),entry.getValue()));
                    }
                }else{
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        //3.堆中元素出队（最小堆出队出来是升序，还要反转）
        List<String> ret=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ret.add(queue.poll().word);
        }
        Collections.reverse(ret);
        return ret;
    }
}
